#if !defined(RASTER_FLOODFILL_H)
#define RASTER_FLOODFILL_H

#include <imglib/bitmap.h>
#include <imglib/raster.h>
#include <raster/algorithm.h>
#include <stdminmax>
#include <cassert>

namespace raster {

typedef img::size_type size_type;

template <class R, class ROP>
struct fillop {
	R &				_raster;
	ROP &			_rop;
	img::bitmap &	_mask;
	fillop(R & r, ROP & rop, img::bitmap & mask)
		: _raster(r), _rop(rop), _mask(mask) { }
	void operator () (int x, int y)
	{
		assert(x >= 0 && x < int(_mask.width()));
		assert(y >= 0 && y < int(_mask.height()));
		size_type sx(x), sy(y);
		_rop(_raster, sx, sy);
		_mask(sx, sy) = true;
	}
};

template <class R, class B, class ROP>
int linefill(R & r, int x0, int y0, int dir, int prev_xl, int prev_xr, B & b, ROP & rop, img::bitmap & mask)
{
	size_type w = mask.width(), h = mask.height();

	fillop<R, ROP> op(r, rop, mask);

	int x, y, xl(x0), xr(x0);
	// search fo the line segment
	while (xl >= 0 && !mask(xl, y0) && !b(r, xl, y0)) --xl;
	while (xr < int(w) && !mask(xr, y0) && !b(r, xr, y0)) ++xr;
	++xl;
	horz_line(xl, xr, y0, op);
	// go in the same direction (+/-)
	y = y0 + dir;
	if (y >= 0 && y < int(h))
		for (x = xl; x < xr; )
			if (!mask(x, y) && !b(r, x, y))
				x = linefill(r, x, y, dir, xl, xr, b, rop, mask);
			else 
				++x;
	// go back
	y = y0 - dir;
	if (y > 0 && y < int(h)) {
		for (x = xl; x < prev_xl; )
			if (!mask(x, y) && !b(r, x, y))
				x = linefill(r, x, y, - dir, xl, xr, b, rop, mask);
			else
				++x;
		for (x = prev_xr; x < xr; )
			if (!mask(x, y) && !b(r, x, y))
				x = linefill(r, x, y, - dir, xl, xr, b, rop, mask);
			else
				++x;
	}
	return xr;
}

template <class R, class B, class ROP>
void floodfill(R & r, size_type x, size_type y, B & b, ROP & rop)
{
	img::bitmap mask;
	size_type w = std::max(mask.width(), r.width()),
		h = std::max(mask.height(), r.height());
	mask.resize(w, h);
	mask.fill(false);
	linefill(r, x, y, 1, x, x, b, rop, mask);
}

} // raster

#endif // RASTER_FLOODFILL_H